# -*- coding: utf-8 -*-

from algorithms import *
import graph
from random import uniform
from time import clock
import math

class Algorithm:
	"""
		A class Algorithm faz a gestão dos algoritmos, recebe como parâmetro o nome do algoritmo e chama a classe correspondente

		Parâmetros de entrada:
		algorithm: Algoritmo a ser analisado
		maxRange: Tamanho n da útilma lista
		hop: Diferença de tamanho entre as listas
			Exemplo:
				Hop = 50
				n da primeira lista = 50
				n da segunda lista = 100
		it: Número de vezes que um algoritmo irá ser testado (Para se obter a média dos tempos obtidos)
	"""

	def __init__(self, algorithm, maxRange, hop, it):
		self.A = []
		self.algorithmNOElements = range(hop, maxRange, hop)
		self.graphInformation = []
		self.it = it
		self.algorithm = algorithm
		self.temporalAnalysis = None
		self.ALL = False


	def chooseAlgorithm(self):
		"""
			Chama a class correspondente à classe do algoritmo necessária
		"""
		if self.algorithm is "insertsort":
			primary.insertsort.InsertSort(self.A)
			self.temporalAnalysis = "squared"
		elif self.algorithm is "bubblesort":
			primary.bubblesort.BubbleSort(self.A)
			self.temporalAnalysis = "squared"
		elif self.algorithm is "heapsort":
			primary.heapsort.HeapSort(self.A)
			self.temporalAnalysis = "logn"
		elif self.algorithm is "mergesort":
			primary.mergesort.MergeSort(self.A)
			self.temporalAnalysis = "logn"
		else:
			primary.quicksort.QuickSort(self.A)
			self.temporalAnalysis = "squared"


	def fillList(self, n):
		"""
			Enche a lista de tamanho n com números randomizados entre 0.0 e 1.0
		"""
		self.A =  [ uniform(0.0, 1.0) for k in xrange(n)]

	def timeMedium(self, T):
		"""
			Com base nos tempos guardados na lista T, retorna a média dos mesmos
		"""
		return reduce(lambda x, y: x + y, T) / len(T)

	def timeVariance(self, T, medium):
		"""
			Com base nos tempos guardados na lista T e a média, retorna a variância
		"""
		return reduce(lambda x, y: x + y, [((k - medium)**2) / (len(T) - 1) for k in T])

	def timeDeviation(self, variance):
		"""
			Retorna o desvio padrão
		"""
		return variance**0.5

	def timeError(self, deviance, n):
		"""
			Retorna o erro da amostra
		"""
		return deviance / (n**0.5)

	def callGraph(self, G):
		"""
			Parâmetro de entrada:
				Lista G que contêm N indices, em que cada indice é um tuplo que contêm o tamanho da lista ordenada e a média dos tempos da mesma

			Variáveis deste método:
				X - Lista com o tamanho das listas que foram ordenadas
				Y - Lista com a média dos tempos
				Z - Valor teórico aplicado ao algoritmo
				V - Variância dos tempos
				D - Desvio Padrão
				E - Erro amostral
				T - Valor tabelar

				Chama o método da classe que desenha o gráfico. O construtor deste método é a lista com o tamanho das listas,  uma
				lista com todos os valores do eixo Y a serem desenhados e os valores da tabela
		"""
		X = [n for n, medium, variance, deviance, error in G]
		Y = [medium for n, medium, variance, deviance, error in G]
		V = [variance for n, medium, variance, deviance, error in G]
		D = [deviance for n, medium, variance, deviance, error in G]
		E = [error for n, medium, variance, deviance, error in G]
		UPPER_ERROR = [(medium + error) for n, medium, variance, deviance, error in G]
		LOWER_ERROR = [(medium - error) for n, medium, variance, deviance, error in G]

		Z = None

		print self.temporalAnalysis
		if self.temporalAnalysis is "squared":
			Z = [(n**2) * (G[len(G) - 1][1] / (G[len(G) - 1][0]**2)) for n, medium, variance, deviance, error in G]
		else:
			Z = [(n*math.log(n, 2) / (G[len(G) - 1][0]*math.log(G[len(G) - 1][0], 2)) * G[len(G) - 1][1]) for n, medium, variance, deviance, error in G]

		T = []
		for k in range(len(X)):
			T.append([X[k], Y[k], Z[k], Y[k] - Z[k], V[k], D[k], E[k]])
		graph.Graph(X, [(Y, "Experimental - {0}".format(self.algorithm), "ro"), (Z, "Teorica - {0}".format(self.algorithm), "b^"),
						(UPPER_ERROR, "(Media + Erro) - {0}".format(self.algorithm), "g-"), (LOWER_ERROR, "(Media - Erro) - {0}".format(self.algorithm), "r-")], T)


	def allAlgorithmAnalysis(self):
		"""
			Método que percorre todos os algoritmos, faz a média de todos e chama o objecto que executa o gráfico sendo o X o número de elementos da lista e o Y
			as médias de tempo entre os 5 algoritmos testados
		"""
		GRAPH_COLORS = ["ro", "bo", "go", "g^", "r^"]
		self.ALL = True
		TOA = ["insertionsort", "quicksort", "bubblesort", "heapsort", "mergesort"]
		TOY = []
		for k in TOA:
			self.algorithm = k
			TOY.append(self.startAnalysis())

		graphYAxis = []
		X = [n for n, medium, variance, deviance, error in TOY[0]]


		temp = 0
		for k in TOY:
			Y = []
			for j in k:
				Y.append(j[1])
			graphYAxis.append((Y, "Experimental - {0}".format(TOA[temp]), GRAPH_COLORS[temp]))
			temp += 1

		graph.Graph(X, graphYAxis)
		
	def startAnalysis(self):
		"""
			Método que faz a análise do algoritmo
			Percorre a lista que contêm o tamanho das listas a serem ordenadas, de seguida entra-se no loop que define que o algoritmo irá ser corrido it vezes
			por cada n escolhido.

			É chamado o método para encher a lista de tamanho n com valores aleatórios, posteriormente é chamado o algoritmo de ordenação e efectuado o 
			cálculo do tempo que o algoritmo demorou a ordenar.

			Retorna uma lista de tuplos em que cada tuplo contêm a lista de tamanho n e o tempo médio que demorou a executar
		"""
		if self.algorithm is "all":
			self.allAlgorithmAnalysis()

		G = []
		for n in self.algorithmNOElements:
			T = []
			for i in range(self.it):
				self.fillList(n)
				T1 = clock()
				self.chooseAlgorithm()
				T2 = clock()
				T.append(T2 - T1)
			medium = self.timeMedium(T)
			variance = self.timeVariance(T, medium)
			deviance = self.timeDeviation(variance)
			error = self.timeError(deviance, self.it)
			G.append((n, medium, variance, deviance, error))

		if self.algorithm is not "all" and not self.ALL:
			self.callGraph(G)
		elif self.ALL:
			return G